//package com.gitee.feizns.explore.data_structure.tree.cus.rbt;
//
//import java.util.Collection;
//import java.util.Set;
//import java.util.TreeSet;
//import java.util.stream.Collectors;
//
///**
// * @author feizns
// * @since 2019/12/26
// */
//public class RbtImpl3<K extends Comparable<K>, V> implements Rbt<RbtImpl3.Node, K, V> {
//
//    public static void main(String[] args) {
//        RbtImpl3 re = new RbtImpl3();
//        re.put(1, "1");
//        re.put(2, "1");
//        re.put(3, "1");
//        re.put(4, "1");
//        re.put(5, "1");
//        re.put(6, "1");
//        re.put(7, "1");
//        re.put(8, "1");
//        re.put(9, "1");
//        re.put(10, "1");
//        re.put(11, "1");
//        re.put(12, "1");
//        re.put(13, "1");
//        re.put(14, "1");
//        re.put(15, "1");
//        re.put(16, "1");
//        re.put(17, "1");
//        re.put(18, "1");
//        re.put(19, "1");
//        re.put(20, "1");
//
//        re.remove(1);
//        re.remove(2);
//        re.remove(3);
//        re.remove(4);
//        re.remove(19);
//        re.remove(5);
//        re.remove(6);
//        re.remove(7);
//        re.remove(8);
//        re.remove(9);
//        re.remove(10);
//        re.remove(11);
//        re.remove(12);
//        re.remove(13);
//        re.remove(14);
//        re.remove(15);
//        re.remove(16);
//        re.remove(17);
//        re.remove(18);
//        re.remove(20);
//    }
//
//    RbtImpl3.Node<K, V> root;
//
//    int size;
//
//    @Override
//    public int size() {
//        return size;
//    }
//
//    @Override
//    public V get(Object key) {
//        Node<K, V> kvNode = find(root, (K) key);
//        return kvNode != null ? kvNode.val() : null;
//    }
//
//    private Node<K, V> find(Node curt, K k) {
//        if ( curt != null ) {
//            int comp = k.compareTo((K) curt.k);
//            if ( comp < 0 )
//                return find(curt.left, k);
//            else if ( comp > 0 )
//                return find(curt.right, k);
//            else
//                return curt;
//        }
//        return null;
//    }
//
//    @Override
//    public V put(K key, V value) {
//        NAndV ret = put(root, key, value);
//        root = ret.n;
//        toBack(root);
//        return ret.v;
//    }
//
//    private NAndV put(RbtImpl3.Node curt, K k, V v) {
//        if ( curt == null ) {
//            size++;
//            return new NAndV(new Node(k, v), null);
//        }
//
//        V oldV;
//        int comp = k.compareTo((K) curt.k);
//        if ( comp < 0 ) {
//            NAndV ret = put(curt.left, k, v);
//            curt.left = ret.n;
//            oldV = ret.v;
//        } else if ( comp > 0 ) {
//            NAndV ret = put(curt.right, k, v);
//            curt.right = ret.n;
//            oldV = ret.v;
//        } else {
//            oldV = (V) curt.v;
//            curt.v = v;
//        }
//
//        curt = balance(curt);
//        return new NAndV(curt, oldV);
//    }
//
//    private static RbtImpl3.Node leftRotate(RbtImpl3.Node node) {
//        RbtImpl3.Node right = node.right;
//        node.right = right.left;
//        right.left = node;
//        right.color = node.color;
//        toRed(node);
//        return right;
//    }
//
//    private static RbtImpl3.Node rightRotate(RbtImpl3.Node node) {
//        RbtImpl3.Node left = node.left;
//        node.left = left.right;
//        left.right = node;
//        left.color = node.color;
//        toRed(node);
//        return left;
//    }
//
//    private void flipColors(RbtImpl3.Node node) {
//        toRed(node);
//        toBack(node.left);
//        toBack(node.right);
//    }
//
//    private static RbtImpl3.Node toRed(RbtImpl3.Node n) {
//        if ( n != null )
//            n.color = RED;
//        return n;
//    }
//
//    private static RbtImpl3.Node toBack(RbtImpl3.Node n) {
//        if ( n != null )
//            n.color = BLACK;
//        return n;
//    }
//
//    private static boolean isR(RbtImpl3.Node n) {
//        return n != null && n.color == RED;
//    }
//
//    private static boolean isB(RbtImpl3.Node n) {
//        return !isR(n);
//    }
//
//    class NAndV {
//        RbtImpl3.Node n;
//        V v;
//        public NAndV(Node n, V v) {
//            this.n = n;
//            this.v = v;
//        }
//    }
//
//    class ReNAndV {
//        RbtImpl3.Node n;
//        V v;
//        public ReNAndV(Node n, V v) {
//            this.n = n;
//            this.v = v;
//        }
//    }
//
//    @Override
//    public V remove(Object key) {
//        ReNAndV nAndV = remove(root, (K) key);
//        root = nAndV.n;
//        toBack(root);
//        return nAndV.v;
//    }
//
//    private ReNAndV remove(RbtImpl3.Node curt, K k) {
//        if ( curt == null )
//            return new ReNAndV(null, null);
//
//        V v;
//        int comp = k.compareTo((K) curt.k);
//        if ( comp < 0 ) {
//            curt = moveToLeft(curt);
//            ReNAndV nAndV = remove(curt.left, k);
//            curt.left = nAndV.n;
//            v = nAndV.v;
//        } else if ( comp > 0 ) {
//            curt = moveToRight(curt);
//            ReNAndV nAndV = remove(curt.right, k);
//            curt.right = nAndV.n;
//            v = nAndV.v;
//        } else {
//            v = (V) curt.v;
//            if ( curt.left == null && curt.right == null ) {
//                size--;
//                curt = null;
//            } else if ( curt.left != null ) {
//                Node max = max(curt.left);
//                curt.k = max.k;
//                curt.v = max.v;
//                curt = moveToLeft(curt);
//                ReNAndV nAndV = remove(curt.left, (K) max.k);
//                curt.left = nAndV.n;
//            } else {
//                Node min = min(curt.left);
//                curt.k = min.k;
//                curt.v = min.v;
//                curt = moveToRight(curt);
//                ReNAndV nAndV = remove(curt.right, (K) min.k);
//                curt.right = nAndV.n;
//            }
//        }
//
//        curt = balance(curt);
//        return new ReNAndV(curt, v);
//    }
//
//    private RbtImpl3.Node balance(RbtImpl3.Node curt) {
//        if ( curt != null ) {
//            if ( isB(curt.left) && isR(curt.right) )
//                curt = leftRotate(curt);
//            if ( isR(curt.left) && isR(curt.left.left) )
//                curt = rightRotate(curt);
//            if ( isR(curt.left) && isR(curt.right) )
//                flipColors(curt);
//        }
//        return curt;
//    }
//
//    private static RbtImpl3.Node moveToLeft(RbtImpl3.Node curt) {
//        if ( curt.left != null ) {
//            if ( isB(curt.left) && isB(curt.left.left) && isB(curt.left.right) ) {
//                if ( curt.right != null ) {
//                    if ( isB(curt.right) && isB(curt.right.left) && isB(curt.right.right) ) {
//                        toBack(curt);
//                        toRed(curt.left);
//                        toRed(curt.right);
//                    } else {
//                        if ( isR(curt.right.left) )
//                            curt.right = rightRotate(curt.right);
//                        curt = leftRotate(curt);
//                        toBack(curt.left);
//                        toRed(curt.left.left);
//                    }
//                }
//            }
//        }
//        return curt;
//    }
//
//    private RbtImpl3.Node moveToRight(RbtImpl3.Node curt) {
//        if ( curt.right != null ) {
//            if ( isB(curt.left) && isB(curt.left.left) && isB(curt.left.right) ) {
//                if ( curt.left != null ) {
//                    if ( isB(curt.left) && isB(curt.left.left) && isB(curt.left.right) ) {
//                        toBack(curt);
//                        toRed(curt.left);
//                        toRed(curt.right);
//                    } else {
//                        if ( isR(curt.left.right) )
//                            curt.left = leftRotate(curt.left);
//                        curt = rightRotate(curt);
//                        toBack(curt.right);
//                        toRed(curt.right.right);
//                    }
//                }
//            }
//        }
//        return curt;
//    }
//
//    private RbtImpl3.Node max(RbtImpl3.Node node) {
//        return node.right == null ? node : max(node.right);
//    }
//
//    private RbtImpl3.Node min(RbtImpl3.Node node) {
//        return node.left == null ? node : min(node.left);
//    }
//
//    @Override
//    public void clear() {
//        root = null;
//        size = 0;
//    }
//
//    @Override
//    public com.gitee.feizns.explore.data_structure.tree.cus.Node root() {
//        return root;
//    }
//
//    @Override
//    public Set<K> keySet() {
//        return entrySet().stream().map(Entry::getKey).collect(Collectors.toSet());
//    }
//
//    @Override
//    public Collection<V> values() {
//        return entrySet().stream().map(Entry::getValue).collect(Collectors.toList());
//    }
//
//    @Override
//    public Set<Entry<K, V>> entrySet() {
//        Set<Entry<K, V>> entries = new TreeSet<>();
//        middleEach((k, v) -> entries.add(new EntryImpl<>(k, v)));
//        return entries;
//    }
//
//    public static class EntryImpl<K, V> implements Entry<K, V> {
//        K k;
//        V v;
//        public EntryImpl(K k, V v) {
//            this.k = k;
//            this.v = v;
//        }
//        @Override
//        public K getKey() {
//            return k;
//        }
//        @Override
//        public V getValue() {
//            return v;
//        }
//        @Override
//        public V setValue(V value) {
//            V old = v;
//            this.v = value;
//            return old;
//        }
//    }
//
//    private static boolean BLACK = true;
//    private static boolean RED = false;
//
//    static class Node<K extends Comparable<K>, V> implements com.gitee.feizns.explore.data_structure.tree.cus.Node<Node, K, V> {
//        boolean color;
//        K k;
//        V v;
//        Node left, right;
//        public Node(K k, V v) {
//            this.k = k;
//            this.v = v;
//        }
//        public Node(K k, V v, boolean color) {
//            this(k, v);
//            this.color = color;
//        }
//        @Override
//        public K key() {
//            return k;
//        }
//        @Override
//        public void key(K k) {
//            this.k = k;
//        }
//        @Override
//        public V val() {
//            return v;
//        }
//        @Override
//        public void val(V v) {
//            this.v = v;
//        }
//        @Override
//        public Node left() {
//            return left;
//        }
//        @Override
//        public void left(Node left) {
//            this.left = left;
//        }
//        @Override
//        public Node right() {
//            return right;
//        }
//        @Override
//        public void right(Node right) {
//            this.right = right;
//        }
//    }
//
//}
